#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

// 线索二叉树

typedef char ElemType;

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag,rtag;
}ThreadNode, *ThreadTree;

ThreadNode *pre=NULL;

// ABD#G##E##CF###
// 构建树结构
// 通过先序创建树
void CreateBiTree(ThreadTree *T){
    char c;
    scanf("%c",&c);
    if('#'==c) {
        *T=NULL; //如果输出的是空格，则表示创建的子树结束
    }
    else
    {
        *T=(ThreadNode*)malloc(sizeof(ThreadNode)); //创建根结点
        (*T)->data=c; //向根结点中输入数据
        CreateBiTree(&((*T)->lchild)); //递归地创建左子树
        CreateBiTree(&((*T)->rchild)); //递归地创建右子树
    }
}

void visit(ThreadNode *q){
    // 左子树为空则建立前驱
    if (q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if (pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre = q;
}

void PreOrder(ThreadTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

